/**
 * (1) 贪心法:
 *
 * 从初始解出发,向给定的目标递推.推进的每一步不是某一固定的递推式,而是做一个当时看似最佳的贪心选择.
 * 不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解.
 *
 * 这种局部贪心的选择在[某些情况下]是可以得出全局最优解的.
 *
 * 对一个最优化问题,我们怎样才能知道它是否适用于贪心算法求解?没有一个通用的方法.但适用于
 * 贪心策略求解的大多数问题都有两个特点:
 *
 * 1.贪心选择性质,每一步都可以把原问题变成一个相似的,但规模更小的问题
 * 2.最优子结构
 *
 * (2) 动态规划 (允许子问题不独立):
 *
 * 贪心法不适合 0-1 背包问题,原因是无法将背包填满,空余的空间降低了它的每磅价值,因此考虑是否要把一件物品
 * 加到背包中时,必须对把加进该物品的子问题的借与不取该物品的子问题的解进行比较.由这种方式形成的子问题导致了
 * 许多重迭的子问题.
 *
 * 参考:算法艺术与信息学竞赛
 */
package com.zk.algo;